package pri.zjy.queue;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author zhangjy
 * @description 前 K 个高频元素
 * @date 2025/6/3 12:01
 */
public class TopKFrequent_347 {

    public static void main(String[] args) {
        // TODO 快排实现

        TopKFrequent_347 topKFrequent347 = new TopKFrequent_347();

        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;

        Arrays.stream(topKFrequent347.topKFrequent3(nums, k)).forEach(System.out::println);
    }

    /**
     * 个解：优先级队列实现小顶堆
     */
    public int[] topKFrequent3(int[] nums, int k) {
        if (k <= 0) return new int[0];

        // 优先级队列int[] 实现小顶堆，[0]是元素值，[1]为出现频率
        // 堆顶元素出现次数是第 k 高

        // 1.记录每个元素出现次数
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 使用computeIfAbsent
            if (countMap.containsKey(nums[i])) {
                countMap.put(nums[i], countMap.get(nums[i]) + 1);
            } else {
                countMap.computeIfAbsent(nums[i], v -> 1);
            }

//            countMap.put(nums[i], countMap.getOrDefault(nums[i], 0) + 1);
        }

        // 2.优先级队列存储出现次数前 k个 多的元素
        // pq以每个元素出现次数从小到大排列
        PriorityQueue<int[]> pq = new PriorityQueue<>((e1, e2) -> e1[1] - e2[1]);
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            // pq存满k个元素，则只存比 队首 出现次数多的元素
            if (pq.size() == k) {
                int[] peek = pq.peek();
                // 队首更小，则出队，后续新元素再入队
                if (peek[1] < entry.getValue()) {
                    // 队首出队
                    pq.poll();
                }
            }
            // 没存满 才入队
            if (pq.size() < k) {
                pq.offer(new int[]{entry.getKey(), entry.getValue()});
            }
        }

        // 3.将答案存入数组ans
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = pq.poll()[0];
        }

        return ans;
    }

    /**
     * dmsxl：优先级队列实现小顶堆
     */
    public int[] topKFrequent2(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数
        //出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) { //小顶堆只需要维持k个元素有序
            if (pq.size() < k) { //小顶堆元素个数小于k个时直接加
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                    pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
            ans[i] = pq.poll()[0];
        }
        return ans;
    }

    /**
     * 参考dmsxl：优先级队列实现小顶堆
     */
    public int[] topKFrequent(int[] nums, int k) {
        // key=nums元素值 value=出现次数
        Map<Integer, Integer> countMap = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            countMap.put(nums[i], countMap.getOrDefault(nums[i], 0) + 1);
        }

        // 创建一个优先级队列，队列存储数组int[]，其中int[0]表示元素，int[1]表示元素出现的次数；该队列根据元素出现的次数 从小到大排列
        PriorityQueue<int[]> queue = new PriorityQueue<>((p1, p2) -> p1[1] - p2[1]);
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (queue.size() < k) {
                // 不足k个元素，则直接插入队列
                queue.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                // 若等于k个，则按小顶堆替换队头元素
                // 堆顶/队头 元素的频率
                int counts = queue.peek()[1];
                if (counts < entry.getValue()) {
                    // 出队
                    queue.poll();
                    // 新元素入队
                    queue.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }

        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            // 按小顶堆顺序弹出
            int[] poll = queue.poll();
            // 记录前k个高频元素
            ans[i] = poll[0];
        }

        return ans;
    }

}
